/*
*
一个括号字符串是一个 非空 且只包含 '(' 和 ')' 的字符串。如果下面 任意 条件为 真 ，那么这个括号字符串就是 合法的 。

字符串是 () 。
字符串可以表示为 AB（A 连接 B），A 和 B 都是合法括号序列。
字符串可以表示为 (A) ，其中 A 是合法括号序列。
给你一个 m x n 的括号网格图矩阵 grid 。网格图中一个 合法括号路径 是满足以下所有条件的一条路径：

路径开始于左上角格子 (0, 0) 。
路径结束于右下角格子 (m - 1, n - 1) 。
路径每次只会向 下 或者向 右 移动。
路径经过的格子组成的括号字符串是 合法 的。
如果网格图中存在一条 合法括号路径 ，请返回 true ，否则返回 false 。

示例 1：

输入：grid = [["(","(","("],[")","(",")"],["(","(",")"],["(","(",")"]]
输出：true
解释：上图展示了两条路径，它们都是合法括号字符串路径。
第一条路径得到的合法字符串是 "()(())" 。
第二条路径得到的合法字符串是 "((()))" 。
注意可能有其他的合法括号字符串路径。
示例 2：

输入：grid = [[")",")"],["(","("]]
输出：false
解释：两条可行路径分别得到 "))(" 和 ")((" 。由于它们都不是合法括号字符串，我们返回 false 。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 100
grid[i][j] 要么是 '(' ，要么是 ')' 。

  - @author ala
  - @date 2024-09-24 12:06
*/
package main

import "fmt"

func main() {
	//grid := [][]byte{{'(', '(', '('}, {')', '(', ')'}, {'(', '(', ')'}, {'(', '(', ')'}}
	//grid := [][]byte{{')', ')'}, {'(', '('}}
	//grid := [][]byte{{'(', ')'}, {'(', ')'}}
	grid := [][]byte{{'(', ')'}}

	fmt.Println(hasValidPath(grid))
}

func hasValidPath(grid [][]byte) bool {
	return V1(grid)
}

/**
 *	1）路线总是横平竖直的走，那把所有路线移到边边上，最多走 M + N - 1 步
 *		左括号 + 1， 右括号 - 1
 *		只有当 M + N - 1 是偶数的时候，才有可能归零
 *		那么路径上至多也只有 (M + N - 1) / 2 个左括号，过了就是条死路
 *	2）dp[i][j]表示走到 (i,j) 点时，所有可能路径的左括号数量
 *		dp[i][j] = make([]int, 0, (M + N - 1) / 2)
 *	3）dp[i][j] = [dp[i-1][j] + grid[i][j], dp[i][j-1] + grid[i][j]]
 *		但要剔除掉其中 < 0 和 > (M + N - 1) / 2 的部分
 *	4）最终，dp[M][N]中，若存在值为0的元素，说明可以找到归零路径
 */
func V1(grid [][]byte) bool {
	M, N := len(grid), len(grid[0])
	total := M + N - 1
	//	如果路径长度是奇数，则无论如何都无法归零
	if total&1 == 1 {
		return false
	}
	up := total >> 1

	dp := make([][][]int, M)
	for i := range dp {
		dp[i] = make([][]int, N)
	}
	for i := 0; i < M; i++ {
		//	该行是否全g
		allG := true
		for j := 0; j < N; j++ {
			v := 1
			if grid[i][j] == ')' {
				v = -1
			}
			dp[i][j] = make([]int, 0, up)
			if i == 0 && j == 0 {
				if v == -1 {
					return false
				} else {
					dp[i][j] = append(dp[i][j], v)
				}
				allG = false
				continue
			}

			//	追加来自上方和左方的左括号数量
			//	相同的值只存一遍，进一步压缩空间
			vis := make([]bool, up+1)
			if i > 0 {
				for _, _v := range dp[i-1][j] {
					s := v + _v
					if s >= 0 && s <= up && !vis[s] {
						dp[i][j] = append(dp[i][j], s)
						vis[s] = true
						allG = false
					}
				}
			}
			if j > 0 {
				for _, _v := range dp[i][j-1] {
					s := v + _v
					if s >= 0 && s <= up && !vis[s] {
						dp[i][j] = append(dp[i][j], s)
						vis[s] = true
						allG = false
					}
				}
			}
		}
		if allG {
			return false
		}
	}
	for _, v := range dp[M-1][N-1] {
		if v == 0 {
			return true
		}
	}
	return false
}
